package com.linyaonan.leetcode.sword_to_offer._30;

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 *
 *  
 *
 * 示例:
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *  
 *
 * 提示：
 *
 * 各函数的调用总次数不超过 20000 次
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.HashMap;
import java.util.LinkedList;

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */
class MinStack {

    /**
     * 堆栈的实现比较简单直接使用现成的LinkedList就可以实现，主要麻烦的地方在于记录当前栈中的最小值
     *
     * 由于栈的特性插入与弹出都是尾部进行的:
     *  1. 所以一个栈中添加一个新值x，StackMin=（StackMin,x）
     *  2. 那么删除一个值时同样只需要将StackMin会退为上一次的StackMin即可，所以需要记录每一次栈的快照对应的StackMin
     *  3. 使用数组的结构记录Stack[0],StackMin Stack[1],StackMin1 等等，简单的做法直接使用Map来记录，key为栈的长度（也可以使用数组实现，复杂度都是O1）
     *
     *  官方解题是使用临时栈，先压入当前栈的最小值，再压入当前值来实现
     *
     */

    LinkedList<Integer> list = new LinkedList<>();

    HashMap<Integer, Integer> mp = new HashMap<>();

    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        int index = list.size();
        if (index == 0) {
            mp.put(0, x);
        } else {
            mp.put(index, Math.min(mp.get(index - 1), x));
        }
        list.push(x);
    }
    
    public void pop() {
        mp.remove(list.size());
        list.pop();
    }
    
    public int top() {
        return list.peek();
    }
    
    public int min() {
        return mp.get(list.size() - 1);
    }
}